(define (make-deque)
  ;; the deque is implemented as a doubly linked list.
  ;; each node in the deque consists of three parts --
  ;; the value of the item, the pointer to the previous node
  ;; and the pointer to the next node.
  (define (make-node value)
    (cons value (cons '() '())))
  (define (node-value node)
    (car node))
  (define (prev-ptr node)
    (cadr node))
  (define (next-ptr node)
    (cddr node))
  (define (set-prev-ptr! node node2)
    (set-car! (cdr node) node2))
  (define (set-next-ptr! node node2)
    (set-cdr! (cdr node) node2))
  
  (let ((front-ptr '())
        (rear-ptr  '()))
    (define (empty-deque?)
      (null? front-ptr))
    (define (front-deque)
      (if (empty-deque?)
          (error "FRONT-DEQUE called with an empty deque")
          (node-value front-ptr)))
    (define (rear-deque)
      (if (empty-deque?)
          (error "FRONT-DEQUE called with an empty deque")
          (node-value rear-ptr)))
    (define (front-insert-deque! value)
      (if (empty-deque?)
          (let ((new-node (make-node value)))
            (set! front-ptr new-node)
            (set! rear-ptr new-node))
          (let ((new-node (make-node value)))
            (set-prev-ptr! front-ptr new-node)
            (set-next-ptr! new-node front-ptr)
            (set! front-ptr new-node))))
    (define (rear-insert-deque! value)
      (if (empty-deque?)
          (let ((new-node (make-node value)))
            (set! front-ptr new-node)
            (set! rear-ptr new-node))
          (let ((new-node (make-node value)))
            (set-next-ptr! rear-ptr new-node)
            (set-prev-ptr! new-node rear-ptr)
            (set! rear-ptr new-node))))
    (define (front-delete-deque!)
      (if (empty-deque?)
          (error "FRONT-DELETE-DEQUE called with an empty deque")
          (begin (set! front-ptr (next-ptr front-ptr))
                 (if (not (null? front-ptr))
                     (set-prev-ptr! front-ptr '())))))
    (define (rear-delete-deque!)
      (if (empty-deque?)
          (error "REAR-DELETE-DEQUE called with an empty deque")
          (begin (set! rear-ptr (prev-ptr rear-ptr))
                 (if (not (null? rear-ptr))
                     (set-next-ptr! rear-ptr '())))))
    (define (print-deque)
      (define (iter node)
        (if (null? node)
            (newline)
            (begin (display (node-value node))
                   (iter (next-ptr node)))))
      (iter front-ptr))

    (define (dispatch m)
      (cond ((eq? m 'empty-deque?) empty-deque?)
            ((eq? m 'front-deque) front-deque)
            ((eq? m 'rear-deque) rear-deque)
            ((eq? m 'front-insert-deque!) front-insert-deque!)
            ((eq? m 'rear-insert-deque!) rear-insert-deque!)
            ((eq? m 'front-delete-deque!) front-delete-deque!)
            ((eq? m 'rear-delete-deque!) rear-delete-deque!)
            ((eq? m 'print-deque) print-deque)
            (else (error "Unknown operation -- " m))))
    dispatch))

(define (empty-deque? deque)
  ((deque 'empty-deque?)))
(define (front-deque deque)
  ((dequq 'front-deque)))
(define (rear-deque deque)
  ((deque 'rear-deque)))
(define (front-insert-deque! deque item)
  ((deque 'front-insert-deque!) item))
(define (rear-insert-deque! deque item)
  ((deque 'rear-insert-deque!) item))
(define (front-delete-deque! deque)
  ((deque 'front-delete-deque!)))
(define (rear-delete-deque! deque)
  ((deque 'rear-delete-deque!)))
(define (print-deque deque)
  ((deque 'print-deque)))


;; tests
(define (test-deque)
  (let ((dq (make-deque)))
    (front-insert-deque! dq 3)
    (print-deque dq)
    (front-insert-deque! dq 2)
    (print-deque dq)
    (rear-insert-deque! dq 4)
    (print-deque dq)
    (rear-delete-deque! dq)
    (print-deque dq)
    (front-delete-deque! dq)
    (print-deque dq)
    (front-delete-deque! dq)
    (print-deque dq)))
